package com.rui.study.algorithm.P_N皇后;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2019-01-12 17:17
 **/
public class Solution {
    List<List<String>> result;
    public List<List<String>> solveNQueens(int n) {
        result = new ArrayList<>(n);
        solveNQueens(0, n, new int[n]);
        return result;
    }

    private void solveNQueens(int row, int n, int[] board) {
        if (row == n) {
            result.add(buildString(board));
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isOK(row, col, board)) {
                board[row] = col;
                solveNQueens(row+1, n, board);
            }
        }
    }

    private boolean isOK(int row, int col, int[] board) {
        int left = col-1, right = col+1;
        for (int i = row-1; i >= 0; i--) {
            if (board[i] == col ||          // 同一列
                    board[i] == left ||   // 左上角
                    board[i] == right) {  // 右上角
                return false;
            }
            left--;
            right++;
        }
        return true;
    }

    private List<String> buildString(int[] board){
        int n = board.length;
        List<String> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            String s = "";
            for (int j = 0; j < n; j++) {
                if (board[i] == j) {
                    s += "Q";
                } else {
                    s += ".";
                }
            }
            list.add(s);
        }
        return list;
    }



    public static void main(String[] args) {
        Solution solution = new Solution();
        long start = System.currentTimeMillis();
        int n = 13;
        List<List<String>> result = solution.solveNQueens(n);
        long end = System.currentTimeMillis();
        for (int i = 0; i < result.size(); i++) {
            System.out.println("解法-" + (i+1));
            List<String> list = result.get(i);
            for (int j = 0; j < n; j++) {
                System.out.println(list.get(j));
            }
        }
        System.out.println("[" + n + "]皇后，耗时：[" + (end - start) + "ms]");
    }


}
